package com.berchen.数据结构.二叉树.线索二叉树;

/**
 * 二叉树
 */
public class BinaryTree {

    public TreeNode root;
    // 为了实现线索化二叉树，需要创建指向当前节点的前驱节点的指针
    private TreeNode pre;

    /**
     * 遍历后序线索二叉树
     */
    public void sufList() {
        TreeNode temp = root;
        // 找到后序遍历开始的节点
        while (temp!=null&&temp.getLeftType() != 1) {
            temp = temp.getLeft();
        }
        TreeNode preNode=null;
        while (temp != null) {

            // 右节点是线索
            if (temp.getRightType()==1){
                System.out.println(temp);
                preNode=temp;
                temp=temp.getRight();
            }else {
                // 如果上个处理的节点是当前节点的右节点
                if(temp.getRight()==preNode){
                    System.out.println(temp);
                    if(temp==root){
                        return;
                    }
                    preNode=temp;
                    temp=temp.getParent();
                }
                else {
                    // 如果从左子节点的进入则找到子树的最左节点
                    temp=temp.getRight();
                    while (temp!=null&&temp.getLeftType()==0){
                        temp=temp.getLeft();
                    }
                }
            }

        }
    }

    public void sufOrder() {
        sufOrder(root);
    }

    /**
     * 后序线索二叉树
     *
     * @param node
     */
    private void sufOrder(TreeNode node) {

        if (node == null) {
            return;
        }
        // 1、线索化左子节点
        sufOrder(node.getLeft());
        // 2、线索化右子节点
        sufOrder(node.getRight());
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }


    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序线索二叉树
     *
     * @param node
     */
    private void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        // 1、线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);  // 让当前节点的左指针指向前驱节点
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        // 2、线索化左子节点
        if (node.getLeftType() != 1) { // 往前遍历 只遍历 前面的子节点 并不遍历前面的前驱节点
            preOrder(node.getLeft());
        }
        // 3、线索化右子节点
        if (node.getRightType() != 1) {
            preOrder(node.getRight());
        }
    }

    /**
     * 遍历前序线索二叉树
     */
    public void preList() {

        TreeNode temp = root;
        while (temp != null) {

            System.out.println(temp);
            // 找到节点的left是前驱节点
            while (temp.getLeftType() == 0) {
                temp = temp.getLeft();
                System.out.println(temp);
            }
            // 找到节点的right是右子节点
            while (temp.getRight() != null && temp.getRightType() == 0) {
                temp = temp.getRight();
                System.out.println(temp);
            }
            temp = temp.getRight();

        }
    }

    /**
     * 遍历中序线索化二叉树 结果就是中序遍历的结果
     */
    public void innList() {
        TreeNode temp = root;
        while (temp != null) {

            // 循环 找到leftType=1的节点，第一个找到的就是8节点
            // 后面随着遍历而变化，因为当leftType=1时没说明该节点是按照线索化处理后的有效节点
            while (temp.getLeftType() == 0) {
                temp = temp.getLeft();
            }
            System.out.println(temp);
            // 如果当前节点的右指针 指向的是后继节点 就一直输出
            while (temp.getRightType() == 1) {
                temp = temp.getRight();
                System.out.println(temp);
            }
            // 替换temp即可
            temp = temp.getRight();
        }

    }


    /**
     * 中序线索化
     */
    public void innOrder() {
        innOrder(root);
    }

    /**
     * 中序线索化
     *
     * @param node
     */
    private void innOrder(TreeNode node) {

        if (node == null) {
            return;
        }
        // 1、线索化左子节点
        innOrder(node.getLeft());
        // 2、线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);  // 让当前节点的左指针指向前驱节点
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;


        // 3、线索化右子节点
        innOrder(node.getRight());
    }

}
